package com.hspedu.newData.dmsxl.数组.二分查找;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-07 
 * @Version: 1.0
 */

public class LC2300咒语和药水的成功对数 {

    // 可以按照这个方法，但是得按照那个查找最左点,但是效率仍然很低
    // todo
    public int[] successfulPairs(int[] spells, int[] potions, long success) {

        Arrays.sort(potions);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < spells.length; i++) {
            int k = spells[i];
            int search = search(potions, k,success);
            list.add(search);
        }

        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    public int search(int[] nums,int k,long success){
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;

        while(i<=j){
            int mid = i + (j - i) /2;
            long x = nums[mid] * k;

            if (x > success){
                j = mid - 1;
            } else if (x < success) {
                i = mid + 1;
            }else {
                candidate = mid;
                j = mid - 1;
            }
        }
        int len = 0;
        if (candidate == -1){
            return nums.length - j - 1;
        }
        return nums.length - candidate;
    }

    @Test
    public void test() {
        // 测试代码
        int x = 56029;
        int y = 68460;
        long z = (long)x*y;
        System.out.println(z);

        successfulPairs(new int[]{5,1,3},new int[]{1,2,3,4,5},7);
    }
}
